/*
 * @lc app=leetcode.cn id=309 lang=cpp
 *
 * [309] 最佳买卖股票时机含冷冻期
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{

public:
    int maxProfit(vector<int> &prices)
    {
        vector<int> dp[3];
        // dp[0][i] 表示 第 i 天持有股票时的最大收益
        // dp[1][i] 表示 第 i 天不持有股票且处于冷冻期的最大收益
        // dp[2][i] 表示 第 i 天不持有股票且不处于冷冻期的最大收益
        //
        // 对于dp[0][i]的股票可以是
        // 1. 在当天买入的（这就要求i-1天不持有股票且不处于冷冻期）
        // 2. 也可以是第i-1天就持有的股票
        // dp[0][i] = max(dp[2][i-1]-prices[i], dp[0][i-1])
        //
        // 对于 dp[1][i] 那么说明第i-1天卖出了股票，这就要求第i-1天是持有股票的
        // dp[1][i] = dp[0][i-1]+prices[i]
        //
        // 对于 dp[2][i] 那么说明
        // 1. 第i-1天不持有股票且不处于冷冻期，且第i天没有买入
        // 2. 第i-1天处于冷冻期
        // dp[2][i] = max(dp[2][i-1], dp[1][i-1])

        // 初始化
        dp[0].push_back(-prices[0]);
        dp[1].push_back(0);
        dp[2].push_back(0);

        // 开始运行
        for (int i = 1; i < prices.size(); i++)
        {
            dp[0].push_back(max(dp[2][i - 1] - prices[i], dp[0][i - 1]));
            dp[1].push_back(dp[0][i - 1] + prices[i]);
            dp[2].push_back(max(dp[2][i - 1], dp[1][i - 1]));
        }
        const int n = prices.size();
        return max(max(dp[0][n-1], dp[1][n-1]), dp[2][n-1]);
    }
};
// @lc code=end
